package com.srunpass.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author srunpass
 * @version Id: 分割回文串, v 0.1 2025/6/4 09:35 srunpass Exp $
 */
public class 分割回文串 {
    boolean[][] f;
    List<List<String>> res = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public static void main(String[] args) {
        分割回文串 m = new 分割回文串();
        System.out.println(m.partition("abaaa"));
    }

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (i == j) {
                    f[i][j] = true;
                    continue;
                }
                f[j][i] = (f[j + 1][i - 1] | (j + 1 == i)) & (s.charAt(i) == s.charAt(j));
            }
        }
        dsf(s, 0);
        return res;
    }

    public void dsf(String s, int index) {
        if (index == n) {
            res.add(new ArrayList<>(ans));
        }
        for (int j = index; j < n; j++) {
            if (f[index][j]) {
                ans.add(s.substring(index, j + 1));
                dsf(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

}